Votre Mission 🎯
Rétablissez la connexion entre $N$ planètes, données par leurs coordonnées 2D, à l'aide d'un réseau de « Hyper-voie » de coût minimal.
- Objectif : Connecter toutes les $N$ planètes (sommets) afin qu'elles soient toutes accessibles (directement ou indirectement).
- Objectif : Trouver la conception du réseau qui minimise le **coût total**.
Analyse 🛰️
Le coût d'une voie (arête) est la distance euclidienne :
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Une voie peut être construite entre n'importe queldeux planètes.
- Cela signifie que nous avons un graphe complet (denses).
La Solution ⚙️
Il s'agit d'un problème classique de Arbre couvrant de poids minimal (MST) problème.
- Algorithme : L'indice recommande l'algorithme de Prim (la version $O(V^2)$), qui est idéale pour les graphes denses.
- Point de départ : Nous commencerons notre algorithme depuis la Planète 0 pour obtenir un résultat cohérent.
Un graphe complet (à gauche) possède toutes les arêtes possibles. L'arbre couvrant de poids minimal (à droite) est le sous-ensemble le moins coûteux d'arêtes reliant tous les sommets.